/*
Copyright 2002, QNX Software Systems Ltd. Unpublished Work All Rights
Reserved.

 
This source code contains confidential information of QNX Software Systems
Ltd. (QSSL). Any use, reproduction, modification, disclosure, distribution
or transfer of this software, or any software which includes or is based
upon any of this code, is only permitted under the terms of the QNX
Confidential Source License version 1.0 (see licensing.qnx.com for details)
or as otherwise expressly authorized by a written license agreement from
QSSL. For more information, please email licensing@qnx.com.
*/
/* lzo1x_oo.ch -- LZO1X compressed data optimizer

   This file is part of the LZO real-time data compression library.

   Copyright (C) 1996-1999 Markus Franz Xaver Johannes Oberhumer

   Markus F.X.J. Oberhumer
   markus.oberhumer@jk.uni-linz.ac.at
 */


#include <stdio.h>
#if 0
#undef NDEBUG
#include <assert.h>
#endif

#define TEST_IP		(ip < ip_end)
#define TEST_OP		(op <= op_end)

#define NO_LIT		LZO_UINT_MAX


/***********************************************************************
//
************************************************************************/

static void copy2(lzo_byte *ip, const lzo_byte *m_pos, lzo_ptrdiff_t off)
{
	assert(off > 0);
	ip[0] = m_pos[0];
	if (off == 1)
		ip[1] = m_pos[0];
	else
		ip[1] = m_pos[1];
}


static void copy3(lzo_byte *ip, const lzo_byte *m_pos, lzo_ptrdiff_t off)
{
	assert(off > 0);
	ip[0] = m_pos[0];
	if (off == 1)
	{
		ip[2] = ip[1] = m_pos[0];
	}
	else if (off == 2)
	{
		ip[1] = m_pos[1];
		ip[2] = m_pos[0];
	}
	else
	{
		ip[1] = m_pos[1];
		ip[2] = m_pos[2];
	}
}


/***********************************************************************
// optimize a block of data.
************************************************************************/

LZO_PUBLIC(int)
DO_OPTIMIZE          (       lzo_byte *in , lzo_uint  in_len,
                             lzo_byte *out, lzo_uint *out_len,
                             lzo_voidp wrkmem )
{
	lzo_byte *op;
	lzo_byte *ip;
	lzo_uint t;
	lzo_byte *m_pos;
	lzo_byte * const ip_end = in + in_len;
	lzo_byte * const op_end = out + *out_len;
	lzo_byte *litp = NULL;
	lzo_uint lit = 0;
	lzo_uint next_lit = NO_LIT;
	lzo_uint nl;
	long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;

	LZO_UNUSED(wrkmem);

#if defined(__LZO_QUERY_OPTIMIZE)
	if (__LZO_IS_OPTIMIZE_QUERY(in,in_len,out,out_len,wrkmem))
		return __LZO_QUERY_OPTIMIZE(in,in_len,out,out_len,wrkmem,0,0);
#endif

	*out_len = 0;

	op = out;
	ip = in;

	assert(in_len >= 3);
	if (*ip > 17)
	{
		t = *ip++ - 17;
		if (t < 4)
			goto match_next;
		goto first_literal_run;
	}
	assert(*ip < 16 || (*ip == 17 && in_len == 3));

	while (TEST_IP && TEST_OP)
	{
		t = *ip++;
		if (t >= 16)
			goto match;
		/* a literal run */
		litp = ip - 1;
		if (t == 0)
		{
			t = 15;
			while (*ip == 0)
				t += 255, ip++;
			t += *ip++;
		}
		lit = t + 3;
		/* copy literals */
copy_literal_run:
		*op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
first_literal_run:
		do *op++ = *ip++; while (--t > 0);


		t = *ip++;

		if (t >= 16)
			goto match;
#if defined(LZO1X)
		m_pos = op - 1 - 0x800;
#elif defined(LZO1Y)
		m_pos = op - 1 - 0x400;
#endif
		m_pos -= t >> 2;
		m_pos -= *ip++ << 2;
		*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
		lit = 0;
		goto match_done;


		/* handle matches */
		while (TEST_IP && TEST_OP)
		{
			if (t < 16)						/* a M1 match */
			{
				m_pos = op - 1;
				m_pos -= t >> 2;
				m_pos -= *ip++ << 2;

				if (litp == NULL)
					goto copy_m1;

				/* assert that there was a match just before */
				assert(lit >= 1 && lit <= 3);
				assert(litp == ip - 2 - lit - 2);
				assert((lzo_uint)(*litp & 3) == lit);
				nl = ip[-2] & 3;
				/* test if a match follows */
				if (nl == 0 && lit == 1 && ip[0] >= 16)
				{
					next_lit = nl;
					/* adjust length of previous short run */
					lit += 2;
					*litp = LZO_BYTE((*litp & ~3) | lit);
					/* copy over the 2 literals that replace the match */
					copy2(ip-2,m_pos,op-m_pos);
					o_m1_a++;
				}
				/* test if a literal run follows */
				else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&
						 (lit + 2 + ip[0] < 16))
				{
					t = *ip++;
					/* remove short run */
					*litp &= ~3;
					/* copy over the 2 literals that replace the match */
					copy2(ip-3+1,m_pos,op-m_pos);
					/* move literals 1 byte ahead */
					litp += 2;
					if (lit > 0)
						lzo_memmove(litp+1,litp,lit);
					/* insert new length of long literal run */
					lit += 2 + t + 3; assert(lit <= 18);
					*litp = LZO_BYTE(lit - 3);

					o_m1_b++;
					*op++ = *m_pos++; *op++ = *m_pos++;
					goto copy_literal_run;
				}
copy_m1:
				*op++ = *m_pos++; *op++ = *m_pos++;
			}
			else
			{
match:
				if (t >= 64)				/* a M2 match */
				{
					m_pos = op - 1;
#if defined(LZO1X)
					m_pos -= (t >> 2) & 7;
					m_pos -= *ip++ << 3;
					t = (t >> 5) - 1;
#elif defined(LZO1Y)
					m_pos -= (t >> 2) & 3;
					m_pos -= *ip++ << 2;
					t = (t >> 4) - 3;
#endif
					if (litp == NULL)
						goto copy_m;

					nl = ip[-2] & 3;
					/* test if in beetween two long literal runs */
					if (t == 1 && lit > 3 && nl == 0 &&
					    ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
					{
						assert(*litp == lit - 3);
						t = *ip++;
						/* copy over the 3 literals that replace the match */
						copy3(ip-1-2,m_pos,op-m_pos);
						/* set new length of previous literal run */
						lit += 3 + t + 3; assert(lit <= 18);
						*litp = LZO_BYTE(lit - 3);
						o_m2++;
						*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
						goto copy_literal_run;
					}
				}
				else
				{
					if (t >= 32)			/* a M3 match */
					{
						t &= 31;
						if (t == 0)
						{
							t = 31;
							while (*ip == 0)
								t += 255, ip++;
							t += *ip++;
						}
						m_pos = op - 1;
						m_pos -= *ip++ >> 2;
						m_pos -= *ip++ << 6;
					}
					else					/* a M4 match */
					{
						m_pos = op;
						m_pos -= (t & 8) << 11;
						t &= 7;
						if (t == 0)
						{
							t = 7;
							while (*ip == 0)
								t += 255, ip++;
							t += *ip++;
						}
						m_pos -= *ip++ >> 2;
						m_pos -= *ip++ << 6;
						if (m_pos == op)
							goto eof_found;
						m_pos -= 0x4000;
					}
					if (litp == NULL)
						goto copy_m;

					nl = ip[-2] & 3;
					/* test if in beetween two matches */
					if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)
					{
						assert(litp == ip - 3 - lit - 2);
						assert((lzo_uint)(*litp & 3) == lit);
						next_lit = nl;
						/* make a previous short run */
						lit += 3;
						*litp = LZO_BYTE((*litp & ~3) | lit);
						/* copy over the 3 literals that replace the match */
						copy3(ip-3,m_pos,op-m_pos);
						o_m3_a++;
					}
					/* test if a literal run follows */
					else if (t == 1 && lit <= 3 && nl == 0 &&
					         ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
					{
						assert(litp == ip - 3 - lit - 2);
						assert((lzo_uint)(*litp & 3) == lit);
						t = *ip++;
						/* remove short run */
						*litp &= ~3;
						/* copy over the 3 literals that replace the match */
						copy3(ip-4+1,m_pos,op-m_pos);
						/* move literals 1 byte ahead */
						litp += 2;
						if (lit > 0)
							lzo_memmove(litp+1,litp,lit);
						/* insert new length of long literal run */
						lit += 3 + t + 3; assert(lit <= 18);
						*litp = LZO_BYTE(lit - 3);

						o_m3_b++;
						*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
						goto copy_literal_run;
					}
				}
copy_m:
				*op++ = *m_pos++; *op++ = *m_pos++;
				do *op++ = *m_pos++; while (--t > 0);
			}

match_done:
			if (next_lit == NO_LIT)
			{
				t = ip[-2] & 3;
				lit = t;
				litp = ip - 2;
			}
			else
				t = next_lit;
			assert(t <= 3);
			next_lit = NO_LIT;
			if (t == 0)
				break;
			/* copy literals */
match_next:
			do *op++ = *ip++; while (--t > 0);
			t = *ip++;
		}
	}

	/* no EOF code was found */
	*out_len = op - out;
	return LZO_E_EOF_NOT_FOUND;

eof_found:
	assert(t == 1);
#if 0
	printf("optimize: %lu %lu  %lu  %lu %lu\n",
	       o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);
#endif
	*out_len = op - out;
	return (ip == ip_end ? LZO_E_OK :
	       (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
}


/*
vi:ts=4
*/

